package class3;

import common.ListNode;
import common.ListNodeUtils;

/**
 * 在单链表和双链表中删除倒数第 k 个节点.
 * 解题思路：
 * 1.先完整走完单链表，判断 k 的值到底比链表长还是短
 * 情况1: 如果 k > 0，则 k 的值大于整个链表长度，不存在到底第 k 个数
 * 情况2: 如果 k = 0，则 k 刚好移动到头节点，因此 head = head.next;
 * 情况3: 如果 k < 0，则 k 实际上在 头节点的基础上，想做走了 N-k 的距离，
 * #     这时候，总头开始走，当 k 负数走到 0 时，就是实际要删除的节点
 */
public class Code11_RemoveLastKthNode {
    public static void main(String[] args) {
        ListNode head = ListNodeUtils.getLinked(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9});
        ListNode listNode = removeLastKthNode(head, 3);
        ListNodeUtils.print(listNode);
    }

    public static ListNode removeLastKthNode(ListNode head, int lastK) {
        if (head == null || lastK < 1) {
            return head;
        }
        ListNode cur = head;
        // 遍历到删除节点
        while (cur != null) {
            lastK--;
            cur = cur.next;
        }
        // 如果此时k 刚好为0，则删除头节点
        if (lastK == 0) {
            head = head.next;
        }
        //
        if (lastK < 0) {
            cur = head;
            while (++lastK != 0) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
        return head;
    }


    public static ListNode removeLastKthNodeDouble(ListNode head, int lastK) {
        if (head == null || lastK < 1) {
            return head;
        }
        ListNode cur = head;
        // 遍历到删除节点
        while (cur != null) {
            lastK--;
            cur = cur.next;
        }
        // 如果此时k 刚好为0，则删除头节点
        if (lastK == 0) {
            head = head.next;
        }
        //
        if (lastK < 0) {
            cur = head;
            while (++lastK != 0) {
                cur = cur.next;
            }
            ListNode newNext = cur.next.next;
            cur.next = newNext;
//            if (newNext != null) {
//                newNext.pre = cur;
//            }
        }
        return head;
    }

}
